Channel coding efficiently introduces redundancy into a sequence of data symbols to promote the reliability of transmission. Two principal techniques employed are block and convolutional coding. See, for example, Error Control Coding--Fundamentals and Applications by S. Lin and D. J. Costello, Prentice-Hall, 1983.
Convolutional coding with Viterbi decoding is widely used as a forward-error-correction technique. Both because of the simplicity of its implementation and the relatively large coding gains that it can achieve. Such coding gains results principally from the ease with which this technique can utilize demodulator soft decisions and thereby provide approximately 2 dB more gain than the corresponding hard decision decoder.
One method of generating convolutional codes involves passing information sequences through shift registers and connecting the register stages to linear algebraic function generators. Selectively combining the outputs of the function generators produces the coded output sequence. A rate R=b/n convolutional code generates n output bits for every b input bits with K b-tuple stages in the encoding shift register. Generation of convolutional codes may also entail selecting codes from a look-up table.
Convolutional codes are a type of tree code. A tree code with no feedback is a trellis code. A linear trellis code is a convolutional code.
A. J. Viterbi introduced Viterbi decoding of convolutional codes in "Error Bounds for convolutional Codes and an Asymptotically Optimum Decoding Algorithm," IEEE Trans. on Info. Theory, Vol. IT-13, pp. 260-269, 1967. Viterbi decoding also appears in G D. Forney, Jr., "The Viterbi Algorithm" Proceedings of the IEEE, Vol. 16, pp. 268-278, 1973.
Forney in "Maximum Likelihood Sequence Estimation of Digital Sequences in the Presence of Intersymbol Interference," IEEE Trans. on Info. Theory, Vol. IT-18, pp. 363-378, 1972, also showed that Viterbi decoding involves maximum likelihood decoding for trellis codes and used it for equalizing channels with intersymbol interference. Viterbi decoding has also been used for demodulation of trellis-coded modulation. See, G. Ungerbock, "Channel Coding With Multilevel Phase Signals," IEEE Trans. on Info. Theory, Vol. IT-28, pp. 55-67, January 1982.
Thus, it can be seen that Viterbi decoding performs advantageously in decoding codes which can be generally characterized by a trellis-like structure.
Good results have been obtained with convolutional codes using soft demodulation outputs, and maximum likelihood decoding with Viterbi decoding (see the Lin and Costello reference, supra). Convolutional codes may be used for continuous data transmission, or by framing data into blocks.
Soft-decision decoding refers to the assignment at the receiver of one of the set of possible code sequences based on multiple-level quantized information at the output of the channel demodulator. Thus, for example, the received noise-corrupted signal from the channel is applied to a set of matched filters corresponding to each possible code word. The outputs of the matched filters are then compared and the code word corresponding to the largest matched filter output is selected as the received code word. "Largest" in this sense typically means largest as a function of samples corresponding to each bit in the received code word.
For a convolutional code with the constraint length K, there are 2.sup.(K-1) =N states, and 2.sup.K -2N state transition branches. In Viterbi decoding, the metric increment for each of these 2N branches needs to be computed at each decoding stage (for each decoded bit) in order to determine survivor paths and update accumulated metrics at the N states. Therefore, the complexity of the Viterbi decoder grows exponentially with the constraint length K. A soft-decision decoder with rate R=1/n requires n2.sup.K =2nN multiplications, 2nN additions and N comparisons at each decoding stage. This limits the efforts to increase coding gain by further increasing the constraint length.
An object of the invention is to improve communication systems. Another object of the invention is to simplify Viterbi decoding.